8、整数删除
题目 整数删除
思路分析
怎么感觉像是模拟……有点难以置信
肯定有个优化的点 但是 暴力模拟一定可以拿一半的分
先写着吧 看看能不能找到优化的点
浪费时间的地方主要是在 找这个最小的数 以及删除后的重新排列下标
一个设想是 用优先队列（小根堆） 加 pair 把所有的{数和下标}都存下来
这样就可以很容易地索引到最小的那个数和它的下标
真进行删除操作比较麻烦 设想是 用一个st数组来标记状态是否已删除
但是更新左右会比较麻烦 干脆把左右也记录下来
用类似于链表的思路 删除一个节点后 左的右等于当前右 右的左等于当前左
居然和正解差不多 但是我这因为是一步一步优化来的 有点冗余 效率较低 有两个数据过不了 但是也够用了
代码实现
#include<bits/stdc++.h>
using namespace std;
struct vi{
int val,idx;
int left, right;
bool operator<(const vi& other)const{
if (val == other.val)
return idx > other.idx;
return val > other.val;
}
};
const int N=5e5+10;
int a[N];
bool st[N];
int L[N],R[N];
priority_queue<vi> minheap;
int main() {
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
L[i]=i-1,R[i]=i+1;
minheap.push({a[i], i, i-1, i+1});
}
while(k--){
auto del = minheap.top();
minheap.pop();
while(st[del.idx] || a[del.idx] != del.val) {
del = minheap.top();
minheap.pop();
}
st[del.idx] = true;
if(del.left >= 1) {
a[del.left]+=del.val;
R[del.left]=R[del.idx];
minheap.push({a[del.left],del.left,L[del.left],R[del.left]});
}
if(del.right <= n) {
a[del.right]+=del.val;
L[del.right]=L[del.idx];
minheap.push({a[del.right],del.right,L[del.right],R[del.right]});
}
}
for(int i = 1; i <= n; i++) {
if(!st[i]) {
cout<<a[i]<<" ";
}
}
return 0;
}
💬 评论